import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author yu
 * @date 2025年05月02日 23:39
 * @Description: 包含深度优先搜索（DFS）方法的类
 */

/**
 * 请输入图的节点数量：
 * 4
 * 请依次输入每个节点的邻接节点，以 -1 结束每个节点的输入：
 * 1 2 -1
 * 3 -1
 * 3 -1
 * -1
 */
public class _10_dfs {
    // 将 result 定义为 static 变量
    private static List<List<Integer>> result = new ArrayList<>();

    public static List<List<Integer>> findAllPaths(int[][] graph) {
        // 初始化起始节点的路径
        List<Integer> path = new ArrayList<>();
        path.add(0);
        // 清空之前的结果
        result.clear();
        dfs(graph, 0, path);
        return result;
    }

    public static void dfs(int[][] graph, int node, List<Integer> path) {
        // 终止条件：到达图的最后一个节点
        if (node == graph.length - 1) {
            // 存放结果
            result.add(new ArrayList<>(path));
            return;
        }

        // 选择：本节点所连接的其他节点
        for (int nextNode : graph[node]) {
            // 处理节点
            path.add(nextNode);
            // 递归
            dfs(graph, nextNode, path);
            // 回溯，撤销处理结果
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入图的节点数量：");
        int n = scanner.nextInt();
        int[][] graph = new int[n][];

        System.out.println("请依次输入每个节点的邻接节点，以 -1 结束每个节点的输入：");
        for (int i = 0; i < n; i++) {
            List<Integer> neighbors = new ArrayList<>();
            int neighbor;
            while ((neighbor = scanner.nextInt()) != -1) {
                neighbors.add(neighbor);
            }
            graph[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
        }

        List<List<Integer>> paths = findAllPaths(graph);
        System.out.println("从节点 0 到节点 " + (graph.length - 1) + " 的所有路径：");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }
        scanner.close();
    }
}